package com.zombies.list.linkedlist.practise;


/**
 *  //单链表实现Josephus(排队出列问题)
 *
 * @author zombies
 * @create 2022-04-22 20:54
 */
public class JosephusDemo<E extends Integer> {
    int n;
    /**
     * 移动 k - 1 个间距
     *
     */
    int k;
    Node<Integer> head;


    public JosephusDemo(int n, int k) {
        this.n = n;
        this.k = k;

        head = new Node(1,null);
        Node<Integer> temp = head;
        for (int i = 2; i <= n; i++) {
            Node<Integer> newNode = new Node(i,null);
            temp.next = newNode;
            temp = newNode;
        }
        temp.next = head;
    }


    private static class Node<E>{
        E data;
        Node<E> next;

        public Node(E e, Node<E> next) {
            this.data = e;
            this.next = next;
        }
    }


    public void show(){
        Node<Integer> temp = head;
        while (temp.next != head){
            System.out.printf("-"+ temp.data + "-");
            temp = temp.next;
        }
        System.out.printf("-"+ temp.data + "-");
        System.out.println();
    }


    /**
     * 疑问：改进一下,head指针跟首元指针指向不一样或许可以改进这个while循环只能到首元结点前面
     *
     *
     */
    public void deleteNum(){

        Node<Integer> temp = head;
        Node<Integer> p = null;
        Integer e;

        while (temp.next != temp){ //转到最后自己指向自己
            for (int i = 0; i < k - 1 ; i++) { // 每次移动k - 1个位置
                p = temp; //每次在temp移动前存储temp的位置，就是temp的小尾巴
                temp = temp.next;
            }
            e = temp.data;
            System.out.printf("->" + e);
            p.next = temp.next;
            temp = temp.next; //目标结点出了队列后temp后移
        }
        System.out.printf("->" + temp.data);

    }


}



